第4题
【说明】
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下：
假设图G存在一个从顶点V0出发的哈密尔顿回路V0——V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
【C代码】
下面是算法的C语言实现。
(1) 常量和变量说明
n：图G中的顶点数
c[][]：图G的邻接矩阵
K：统计变量，当期已经访问的定点数为k+1
x[k]：第k个访问的顶点编号，从0开始
Visited[x[k]]：第k个顶点的访问标志，0表示未访问，1表示已访问
(2) C程序
一个无向连通图G点上的哈密尔顿(Hamiltion)回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下：
假设图G存在一个从顶点V0出发的哈密尔顿回路V0——V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；直到找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。
【C代码】
下面是算法的C语言实现。
(1) 常量和变量说明
n：图G中的顶点数
c[][]：图G的邻接矩阵
K：统计变量，当期已经访问的定点数为k+1
x[k]：第k个访问的顶点编号，从0开始
Visited[x[k]]：第k个顶点的访问标志，0表示未访问，1表示已访问
(2) C程序
【问题：4.1】(10分)
根据题干说明。填充C代码中的空(1)~(5).
根据题干说明。填充C代码中的空(1)~(5).
【问题：4.2】(5分)
根据题干说明和C代码，算法采用的设计策略为(6)，该方法在遍历图的顶点时，采用的是(7)方法(深度优先或广度优先)。
根据题干说明和C代码，算法采用的设计策略为(6)，该方法在遍历图的顶点时，采用的是(7)方法(深度优先或广度优先)。
2017年 下半年 下午试卷 案例
正确答案：
你的答案：
请先在App中激活(应用市场搜“软考真题”)
知识点：
试卷：
2017年 下半年 下午试卷 案例
笔记
请先在App中激活(应用市场搜“软考真题”)
2019-11-07
微风佛面
请先在App中激活(应用市场搜“软考真题”)
2020-10-31
微风佛面
请先在App中激活(应用市场搜“软考真题”)
2020-10-31
微风佛面
请先在App中激活(应用市场搜“软考真题”)
2020-10-31
小左
请先在App中激活(应用市场搜“软考真题”)
2021-04-07
奕筱
请先在App中激活(应用市场搜“软考真题”)
2021-05-27